package Partition;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-02-21
 * Time:16:38
 * Text：数组中的逆序对
 */
public class Text6 {
    static int count=0;
    static int[] tmp;
    public static void qsort(int[] nums,int l,int r){
        if(l>=r) return;
        int mid=(l+r)/2;
        qsort(nums,l,mid);
        qsort(nums,mid+1,r);

        int cur1=l,cur2=mid+1,i=0;
        while(cur1<=mid){
            if(nums[cur1]>nums[cur2]){
                count++;
                cur2++;
            }else{
                cur1++;
                cur2=mid+1;
            }
             if(cur2>r){
                cur1++;
                cur2=mid+1;
            }
        }
        cur1=l;cur2=mid+1;
        while(cur1<=mid && cur2<=r){
            tmp[i++]=nums[cur1]>=nums[cur2]?nums[cur2++]:nums[cur1++];
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=r) {
            tmp[i++]=nums[cur2++];
        }
        for(int j=l;j<=r;j++){
            nums[j]=tmp[j-l];
        }

    }
    //代码简洁
    public static int qsort2(int[] nums,int l,int r) {
        if(l>=r) return 0;
        int ret=0;
        int mid=(l+r)>>1;
        ret+=qsort2(nums,l,mid);
        ret+=qsort2(nums,mid+1,r);

        int cur1=l,cur2=mid+1,i=0;
        while(cur1<=mid && cur2<=r){
            if(nums[cur1]<=nums[cur2]){
                tmp[i++]=nums[cur1++];
            }
            else{
                ret+=mid-cur1+1;
                tmp[i++]=nums[cur2++];
            }
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=r) {
            tmp[i++]=nums[cur2++];
        }
        for(int j=l;j<=r;j++){
            nums[j]=tmp[j-l];
        }
        return ret;
    }
    public static void main(String[] args) {
        int[] array={7,5,4,2,1,8,9};
        tmp=new int[array.length];
        //qsort(array,0, array.length-1);
        System.out.println(qsort2(array,0, array.length-1));
        System.out.println(count);
    }
}
